﻿#ifndef MYTINYSTL_BASIC_STRING_H_
#define MYTINYSTL_BASIC_STRING_H_

// 这个头文件包含一个模板类 basic_string
// 用于表示字符串类型

#include <iostream>

#include <deal.II/mystl/iterator.h>
#include <deal.II/mystl/memory.h>
#include <deal.II/mystl/functional.h>
#include <deal.II/mystl/exceptdef.h>


#include <deal.II/base/config.h>

DEAL_II_NAMESPACE_OPEN

namespace mystl
{

  // char_traits

  template <class CharType>
  struct char_traits
  {
    typedef CharType char_type;

    static size_t length(const char_type *str)
    {
      size_t len = 0;
      for (; *str != char_type(0); ++str)
        ++len;
      return len;
    }

    static int compare(const char_type *s1, const char_type *s2, size_t n)
    {
      for (; n != 0; --n, ++s1, ++s2)
      {
        if (*s1 < *s2)
          return -1;
        if (*s2 < *s1)
          return 1;
      }
      return 0;
    }

    static char_type *copy(char_type *dst, const char_type *src, size_t n)
    {
      MYSTL_DEBUG(src + n <= dst || dst + n <= src);
      char_type *r = dst;
      for (; n != 0; --n, ++dst, ++src)
        *dst = *src;
      return r;
    }

    static char_type *move(char_type *dst, const char_type *src, size_t n)
    {
      char_type *r = dst;
      if (dst < src)
      {
        for (; n != 0; --n, ++dst, ++src)
          *dst = *src;
      }
      else if (src < dst)
      {
        dst += n;
        src += n;
        for (; n != 0; --n)
          *--dst = *--src;
      }
      return r;
    }

    static char_type *fill(char_type *dst, char_type ch, size_t count)
    {
      char_type *r = dst;
      for (; count > 0; --count, ++dst)
        *dst = ch;
      return r;
    }
  };

  // Partialized. char_traits<char>
  template <>
  struct char_traits<char>
  {
    typedef char char_type;

    static size_t length(const char_type *str) noexcept
    {
      return std::strlen(str);
    }

    static int compare(const char_type *s1, const char_type *s2, size_t n) noexcept
    {
      return std::memcmp(s1, s2, n);
    }

    static char_type *copy(char_type *dst, const char_type *src, size_t n) noexcept
    {
      MYSTL_DEBUG(src + n <= dst || dst + n <= src);
      return static_cast<char_type *>(std::memcpy(dst, src, n));
    }

    static char_type *move(char_type *dst, const char_type *src, size_t n) noexcept
    {
      return static_cast<char_type *>(std::memmove(dst, src, n));
    }

    static char_type *fill(char_type *dst, char_type ch, size_t count) noexcept
    {
      return static_cast<char_type *>(std::memset(dst, ch, count));
    }
  };

  // Partialized. char_traits<wchar_t>
  template <>
  struct char_traits<wchar_t>
  {
    typedef wchar_t char_type;

    static size_t length(const char_type *str) noexcept
    {
      return std::wcslen(str);
    }

    static int compare(const char_type *s1, const char_type *s2, size_t n) noexcept
    {
      return std::wmemcmp(s1, s2, n);
    }

    static char_type *copy(char_type *dst, const char_type *src, size_t n) noexcept
    {
      MYSTL_DEBUG(src + n <= dst || dst + n <= src);
      return static_cast<char_type *>(std::wmemcpy(dst, src, n));
    }

    static char_type *move(char_type *dst, const char_type *src, size_t n) noexcept
    {
      return static_cast<char_type *>(std::wmemmove(dst, src, n));
    }

    static char_type *fill(char_type *dst, char_type ch, size_t count) noexcept
    {
      return static_cast<char_type *>(std::wmemset(dst, ch, count));
    }
  };

  // Partialized. char_traits<char16_t>
  template <>
  struct char_traits<char16_t>
  {
    typedef char16_t char_type;

    static size_t length(const char_type *str) noexcept
    {
      size_t len = 0;
      for (; *str != char_type(0); ++str)
        ++len;
      return len;
    }

    static int compare(const char_type *s1, const char_type *s2, size_t n) noexcept
    {
      for (; n != 0; --n, ++s1, ++s2)
      {
        if (*s1 < *s2)
          return -1;
        if (*s2 < *s1)
          return 1;
      }
      return 0;
    }

    static char_type *copy(char_type *dst, const char_type *src, size_t n) noexcept
    {
      MYSTL_DEBUG(src + n <= dst || dst + n <= src);
      char_type *r = dst;
      for (; n != 0; --n, ++dst, ++src)
        *dst = *src;
      return r;
    }

    static char_type *move(char_type *dst, const char_type *src, size_t n) noexcept
    {
      char_type *r = dst;
      if (dst < src)
      {
        for (; n != 0; --n, ++dst, ++src)
          *dst = *src;
      }
      else if (src < dst)
      {
        dst += n;
        src += n;
        for (; n != 0; --n)
          *--dst = *--src;
      }
      return r;
    }

    static char_type *fill(char_type *dst, char_type ch, size_t count) noexcept
    {
      char_type *r = dst;
      for (; count > 0; --count, ++dst)
        *dst = ch;
      return r;
    }
  };

  // Partialized. char_traits<char32_t>
  template <>
  struct char_traits<char32_t>
  {
    typedef char32_t char_type;

    static size_t length(const char_type *str) noexcept
    {
      size_t len = 0;
      for (; *str != char_type(0); ++str)
        ++len;
      return len;
    }

    static int compare(const char_type *s1, const char_type *s2, size_t n) noexcept
    {
      for (; n != 0; --n, ++s1, ++s2)
      {
        if (*s1 < *s2)
          return -1;
        if (*s2 < *s1)
          return 1;
      }
      return 0;
    }

    static char_type *copy(char_type *dst, const char_type *src, size_t n) noexcept
    {
      MYSTL_DEBUG(src + n <= dst || dst + n <= src);
      char_type *r = dst;
      for (; n != 0; --n, ++dst, ++src)
        *dst = *src;
      return r;
    }

    static char_type *move(char_type *dst, const char_type *src, size_t n) noexcept
    {
      char_type *r = dst;
      if (dst < src)
      {
        for (; n != 0; --n, ++dst, ++src)
          *dst = *src;
      }
      else if (src < dst)
      {
        dst += n;
        src += n;
        for (; n != 0; --n)
          *--dst = *--src;
      }
      return r;
    }

    static char_type *fill(char_type *dst, char_type ch, size_t count) noexcept
    {
      char_type *r = dst;
      for (; count > 0; --count, ++dst)
        *dst = ch;
      return r;
    }
  };

// 初始化 basic_string 尝试分配的最小 buffer 大小，可能被忽略
#define STRING_INIT_SIZE 32

  // 模板类 basic_string
  // 参数一代表字符类型，参数二代表萃取字符类型的方式，缺省使用 mystl::char_traits
  template <class CharType, class CharTraits = mystl::char_traits<CharType>>
  class basic_string
  {
  public:
    typedef CharTraits traits_type;
    typedef CharTraits char_traits;

    typedef mystl::allocator<CharType> allocator_type;
    typedef mystl::allocator<CharType> data_allocator;

    typedef typename allocator_type::value_type value_type;
    typedef typename allocator_type::pointer pointer;
    typedef typename allocator_type::const_pointer const_pointer;
    typedef typename allocator_type::reference reference;
    typedef typename allocator_type::const_reference const_reference;
    typedef typename allocator_type::size_type size_type;
    typedef typename allocator_type::difference_type difference_type;

    typedef value_type *iterator;
    typedef const value_type *const_iterator;
    typedef mystl::reverse_iterator<iterator> reverse_iterator;
    typedef mystl::reverse_iterator<const_iterator> const_reverse_iterator;

    allocator_type get_allocator() { return allocator_type(); }

    static_assert(std::is_pod<CharType>::value, "Character type of basic_string must be a POD");
    static_assert(std::is_same<CharType, typename traits_type::char_type>::value,
                  "CharType must be same as traits_type::char_type");

  public:
    // 末尾位置的值，例:
    // if (str.find('a') != string::npos) { /* do something */ }
    static constexpr size_type npos = static_cast<size_type>(-1);

  private:
    iterator buffer_; // 储存字符串的起始位置
    size_type size_;  // 大小
    size_type cap_;   // 容量

  public:
    // 构造、复制、移动、析构函数

    basic_string() noexcept
    {
      try_init();
    }

    basic_string(size_type n, value_type ch)
        : buffer_(nullptr), size_(0), cap_(0)
    {
      fill_init(n, ch);
    }

    basic_string(const basic_string &other, size_type pos)
        : buffer_(nullptr), size_(0), cap_(0)
    {
      init_from(other.buffer_, pos, other.size_ - pos);
    }
    basic_string(const basic_string &other, size_type pos, size_type count)
        : buffer_(nullptr), size_(0), cap_(0)
    {
      init_from(other.buffer_, pos, count);
    }

    basic_string(const_pointer str)
        : buffer_(nullptr), size_(0), cap_(0)
    {
      init_from(str, 0, char_traits::length(str));
    }
    basic_string(const_pointer str, size_type count)
        : buffer_(nullptr), size_(0), cap_(0)
    {
      init_from(str, 0, count);
    }

    template <class Iter, typename std::enable_if<
                              mystl::is_input_iterator<Iter>::value, int>::type = 0>
    basic_string(Iter first, Iter last)
    {
      copy_init(first, last, iterator_category(first));
    }

    basic_string(const basic_string &rhs)
        : buffer_(nullptr), size_(0), cap_(0)
    {
      init_from(rhs.buffer_, 0, rhs.size_);
    }
    basic_string(basic_string &&rhs) noexcept
        : buffer_(rhs.buffer_), size_(rhs.size_), cap_(rhs.cap_)
    {
      rhs.buffer_ = nullptr;
      rhs.size_ = 0;
      rhs.cap_ = 0;
    }

    basic_string &operator=(const basic_string &rhs);
    basic_string &operator=(basic_string &&rhs) noexcept;

    basic_string &operator=(const_pointer str);
    basic_string &operator=(value_type ch);

    ~basic_string() { destroy_buffer(); }

  public:
    // 迭代器相关操作
    iterator begin() noexcept
    {
      return buffer_;
    }
    const_iterator begin() const noexcept
    {
      return buffer_;
    }
    iterator end() noexcept
    {
      return buffer_ + size_;
    }
    const_iterator end() const noexcept
    {
      return buffer_ + size_;
    }

    reverse_iterator rbegin() noexcept
    {
      return reverse_iterator(end());
    }
    const_reverse_iterator rbegin() const noexcept
    {
      return const_reverse_iterator(end());
    }
    reverse_iterator rend() noexcept
    {
      return reverse_iterator(begin());
    }
    const_reverse_iterator rend() const noexcept
    {
      return const_reverse_iterator(begin());
    }

    const_iterator cbegin() const noexcept
    {
      return begin();
    }
    const_iterator cend() const noexcept
    {
      return end();
    }
    const_reverse_iterator crbegin() const noexcept
    {
      return rbegin();
    }
    const_reverse_iterator crend() const noexcept
    {
      return rend();
    }

    // 容量相关操作
    bool empty() const noexcept
    {
      return size_ == 0;
    }

    size_type size() const noexcept
    {
      return size_;
    }
    size_type length() const noexcept
    {
      return size_;
    }
    size_type capacity() const noexcept
    {
      return cap_;
    }
    size_type max_size() const noexcept
    {
      return static_cast<size_type>(-1);
    }

    void reserve(size_type n);
    void shrink_to_fit();

    // 访问元素相关操作
    reference operator[](size_type n)
    {
      MYSTL_DEBUG(n <= size_);
      if (n == size_)
        *(buffer_ + n) = value_type();
      return *(buffer_ + n);
    }
    const_reference operator[](size_type n) const
    {
      MYSTL_DEBUG(n <= size_);
      if (n == size_)
        *(buffer_ + n) = value_type();
      return *(buffer_ + n);
    }

    reference at(size_type n)
    {
      THROW_OUT_OF_RANGE_IF(n >= size_, "basic_string<Char, Traits>::at()"
                                        "subscript out of range");
      return (*this)[n];
    }
    const_reference at(size_type n) const
    {
      THROW_OUT_OF_RANGE_IF(n >= size_, "basic_string<Char, Traits>::at()"
                                        "subscript out of range");
      return (*this)[n];
    }

    reference front()
    {
      MYSTL_DEBUG(!empty());
      return *begin();
    }
    const_reference front() const
    {
      MYSTL_DEBUG(!empty());
      return *begin();
    }

    reference back()
    {
      MYSTL_DEBUG(!empty());
      return *(end() - 1);
    }
    const_reference back() const
    {
      MYSTL_DEBUG(!empty());
      return *(end() - 1);
    }

    const_pointer data() const noexcept
    {
      return to_raw_pointer();
    }
    const_pointer c_str() const noexcept
    {
      return to_raw_pointer();
    }

    // 添加删除相关操作

    // insert
    iterator insert(const_iterator pos, value_type ch);
    iterator insert(const_iterator pos, size_type count, value_type ch);

    template <class Iter>
    iterator insert(const_iterator pos, Iter first, Iter last);

    // push_back / pop_back
    void push_back(value_type ch)
    {
      append(1, ch);
    }
    void pop_back()
    {
      MYSTL_DEBUG(!empty());
      --size_;
    }

    // append
    basic_string &append(size_type count, value_type ch);

    basic_string &append(const basic_string &str)
    {
      return append(str, 0, str.size_);
    }
    basic_string &append(const basic_string &str, size_type pos)
    {
      return append(str, pos, str.size_ - pos);
    }
    basic_string &append(const basic_string &str, size_type pos, size_type count);

    basic_string &append(const_pointer s)
    {
      return append(s, char_traits::length(s));
    }
    basic_string &append(const_pointer s, size_type count);

    template <class Iter, typename std::enable_if<
                              mystl::is_input_iterator<Iter>::value, int>::type = 0>
    basic_string &append(Iter first, Iter last)
    {
      return append_range(first, last);
    }

    // erase /clear
    iterator erase(const_iterator pos);
    iterator erase(const_iterator first, const_iterator last);

    // resize
    void resize(size_type count)
    {
      resize(count, value_type());
    }
    void resize(size_type count, value_type ch);

    void clear() noexcept
    {
      size_ = 0;
    }

    // basic_string 相关操作

    // compare
    int compare(const basic_string &other) const;
    int compare(size_type pos1, size_type count1, const basic_string &other) const;
    int compare(size_type pos1, size_type count1, const basic_string &other,
                size_type pos2, size_type count2 = npos) const;
    int compare(const_pointer s) const;
    int compare(size_type pos1, size_type count1, const_pointer s) const;
    int compare(size_type pos1, size_type count1, const_pointer s, size_type count2) const;

    // substr
    basic_string substr(size_type index, size_type count = npos)
    {
      count = mystl::min(count, size_ - index);
      return basic_string(buffer_ + index, buffer_ + index + count);
    }

    // replace
    basic_string &replace(size_type pos, size_type count, const basic_string &str)
    {
      THROW_OUT_OF_RANGE_IF(pos > size_, "basic_string<Char, Traits>::replace's pos out of range");
      return replace_cstr(buffer_ + pos, count, str.buffer_, str.size_);
    }
    basic_string &replace(const_iterator first, const_iterator last, const basic_string &str)
    {
      MYSTL_DEBUG(begin() <= first && last <= end() && first <= last);
      return replace_cstr(first, static_cast<size_type>(last - first), str.buffer_, str.size_);
    }

    basic_string &replace(size_type pos, size_type count, const_pointer str)
    {
      THROW_OUT_OF_RANGE_IF(pos > size_, "basic_string<Char, Traits>::replace's pos out of range");
      return replace_cstr(buffer_ + pos, count, str, char_traits::length(str));
    }
    basic_string &replace(const_iterator first, const_iterator last, const_pointer str)
    {
      MYSTL_DEBUG(begin() <= first && last <= end() && first <= last);
      return replace_cstr(first, static_cast<size_type>(last - first), str, char_traits::length(str));
    }

    basic_string &replace(size_type pos, size_type count, const_pointer str, size_type count2)
    {
      THROW_OUT_OF_RANGE_IF(pos > size_, "basic_string<Char, Traits>::replace's pos out of range");
      return replace_cstr(buffer_ + pos, count, str, count2);
    }
    basic_string &replace(const_iterator first, const_iterator last, const_pointer str, size_type count)
    {
      MYSTL_DEBUG(begin() <= first && last <= end() && first <= last);
      return replace_cstr(first, static_cast<size_type>(last - first), str, count);
    }

    basic_string &replace(size_type pos, size_type count, size_type count2, value_type ch)
    {
      THROW_OUT_OF_RANGE_IF(pos > size_, "basic_string<Char, Traits>::replace's pos out of range");
      return replace_fill(buffer_ + pos, count, count2, ch);
    }
    basic_string &replace(const_iterator first, const_iterator last, size_type count, value_type ch)
    {
      MYSTL_DEBUG(begin() <= first && last <= end() && first <= last);
      return replace_fill(first, static_cast<size_type>(last - first), count, ch);
    }

    basic_string &replace(size_type pos1, size_type count1, const basic_string &str,
                          size_type pos2, size_type count2 = npos)
    {
      THROW_OUT_OF_RANGE_IF(pos1 > size_ || pos2 > str.size_,
                            "basic_string<Char, Traits>::replace's pos out of range");
      return replace_cstr(buffer_ + pos1, count1, str.buffer_ + pos2, count2);
    }

    template <class Iter, typename std::enable_if<
                              mystl::is_input_iterator<Iter>::value, int>::type = 0>
    basic_string &replace(const_iterator first, const_iterator last, Iter first2, Iter last2)
    {
      MYSTL_DEBUG(begin() <= first && last <= end() && first <= last);
      return replace_copy(first, last, first2, last2);
    }

    // reverse
    void reverse() noexcept;

    // swap
    void swap(basic_string &rhs) noexcept;

    // 查找相关操作

    // find
    size_type find(value_type ch, size_type pos = 0) const noexcept;
    size_type find(const_pointer str, size_type pos = 0) const noexcept;
    size_type find(const_pointer str, size_type pos, size_type count) const noexcept;
    size_type find(const basic_string &str, size_type pos = 0) const noexcept;

    // rfind
    size_type rfind(value_type ch, size_type pos = npos) const noexcept;
    size_type rfind(const_pointer str, size_type pos = npos) const noexcept;
    size_type rfind(const_pointer str, size_type pos, size_type count) const noexcept;
    size_type rfind(const basic_string &str, size_type pos = npos) const noexcept;

    // find_first_of
    size_type find_first_of(value_type ch, size_type pos = 0) const noexcept;
    size_type find_first_of(const_pointer s, size_type pos = 0) const noexcept;
    size_type find_first_of(const_pointer s, size_type pos, size_type count) const noexcept;
    size_type find_first_of(const basic_string &str, size_type pos = 0) const noexcept;

    // find_first_not_of
    size_type find_first_not_of(value_type ch, size_type pos = 0) const noexcept;
    size_type find_first_not_of(const_pointer s, size_type pos = 0) const noexcept;
    size_type find_first_not_of(const_pointer s, size_type pos, size_type count) const noexcept;
    size_type find_first_not_of(const basic_string &str, size_type pos = 0) const noexcept;

    // find_last_of
    size_type find_last_of(value_type ch, size_type pos = 0) const noexcept;
    size_type find_last_of(const_pointer s, size_type pos = 0) const noexcept;
    size_type find_last_of(const_pointer s, size_type pos, size_type count) const noexcept;
    size_type find_last_of(const basic_string &str, size_type pos = 0) const noexcept;

    // find_last_not_of
    size_type find_last_not_of(value_type ch, size_type pos = 0) const noexcept;
    size_type find_last_not_of(const_pointer s, size_type pos = 0) const noexcept;
    size_type find_last_not_of(const_pointer s, size_type pos, size_type count) const noexcept;
    size_type find_last_not_of(const basic_string &str, size_type pos = 0) const noexcept;

    // count
    size_type count(value_type ch, size_type pos = 0) const noexcept;

  public:
    // 重载 operator+=
    basic_string &operator+=(const basic_string &str)
    {
      return append(str);
    }
    basic_string &operator+=(value_type ch)
    {
      return append(1, ch);
    }
    basic_string &operator+=(const_pointer str)
    {
      return append(str, str + char_traits::length(str));
    }

    // 重载 operator >> / operatror <<

    friend std::istream &operator>>(std::istream &is, basic_string &str)
    {
      value_type *buf = new value_type[4096];
      is >> buf;
      basic_string tmp(buf);
      str = std::move(tmp);
      delete[] buf;
      return is;
    }

    friend std::ostream &operator<<(std::ostream &os, const basic_string &str)
    {
      for (size_type i = 0; i < str.size_; ++i)
        os << *(str.buffer_ + i);
      return os;
    }

  private:
    // helper functions

    // init / destroy
    void try_init() noexcept;

    void fill_init(size_type n, value_type ch);

    template <class Iter>
    void copy_init(Iter first, Iter last, mystl::input_iterator_tag);
    template <class Iter>
    void copy_init(Iter first, Iter last, mystl::forward_iterator_tag);

    void init_from(const_pointer src, size_type pos, size_type n);

    void destroy_buffer();

    // get raw pointer
    const_pointer to_raw_pointer() const;

    // shrink_to_fit
    void reinsert(size_type size);

    // append
    template <class Iter>
    basic_string &append_range(Iter first, Iter last);

    // compare
    int compare_cstr(const_pointer s1, size_type n1, const_pointer s2, size_type n2) const;

    // replace
    basic_string &replace_cstr(const_iterator first, size_type count1, const_pointer str, size_type count2);
    basic_string &replace_fill(const_iterator first, size_type count1, size_type count2, value_type ch);
    template <class Iter>
    basic_string &replace_copy(const_iterator first, const_iterator last, Iter first2, Iter last2);

    // reallocate
    void reallocate(size_type need);
    iterator reallocate_and_fill(iterator pos, size_type n, value_type ch);
    iterator reallocate_and_copy(iterator pos, const_iterator first, const_iterator last);
  };

  /*****************************************************************************************/

  // 复制赋值操作符
  template <class CharType, class CharTraits>
  basic_string<CharType, CharTraits> &
  basic_string<CharType, CharTraits>::
  operator=(const basic_string &rhs)
  {
    if (this != &rhs)
    {
      basic_string tmp(rhs);
      swap(tmp);
    }
    return *this;
  }

  // 移动赋值操作符
  template <class CharType, class CharTraits>
  basic_string<CharType, CharTraits> &
  basic_string<CharType, CharTraits>::
  operator=(basic_string &&rhs) noexcept
  {
    destroy_buffer();
    buffer_ = rhs.buffer_;
    size_ = rhs.size_;
    cap_ = rhs.cap_;
    rhs.buffer_ = nullptr;
    rhs.size_ = 0;
    rhs.cap_ = 0;
    return *this;
  }

  // 用一个字符串赋值
  template <class CharType, class CharTraits>
  basic_string<CharType, CharTraits> &
  basic_string<CharType, CharTraits>::
  operator=(const_pointer str)
  {
    const size_type len = char_traits::length(str);
    if (cap_ < len)
    {
      auto new_buffer = data_allocator::allocate(len + 1);
      data_allocator::deallocate(buffer_);
      buffer_ = new_buffer;
      cap_ = len + 1;
    }
    char_traits::copy(buffer_, str, len);
    size_ = len;
    return *this;
  }

  // 用一个字符赋值
  template <class CharType, class CharTraits>
  basic_string<CharType, CharTraits> &
  basic_string<CharType, CharTraits>::
  operator=(value_type ch)
  {
    if (cap_ < 1)
    {
      auto new_buffer = data_allocator::allocate(2);
      data_allocator::deallocate(buffer_);
      buffer_ = new_buffer;
      cap_ = 2;
    }
    *buffer_ = ch;
    size_ = 1;
    return *this;
  }

  // 预留储存空间
  template <class CharType, class CharTraits>
  void basic_string<CharType, CharTraits>::
      reserve(size_type n)
  {
    if (cap_ < n)
    {
      THROW_LENGTH_ERROR_IF(n > max_size(), "n can not larger than max_size()"
                                            "in basic_string<Char,Traits>::reserve(n)");
      auto new_buffer = data_allocator::allocate(n);
      char_traits::move(new_buffer, buffer_, size_);
      buffer_ = new_buffer;
      cap_ = n;
    }
  }

  // 减少不用的空间
  template <class CharType, class CharTraits>
  void basic_string<CharType, CharTraits>::
      shrink_to_fit()
  {
    if (size_ != cap_)
    {
      reinsert(size_);
    }
  }

  // 在 pos 处插入一个元素
  template <class CharType, class CharTraits>
  typename basic_string<CharType, CharTraits>::iterator
  basic_string<CharType, CharTraits>::
      insert(const_iterator pos, value_type ch)
  {
    iterator r = const_cast<iterator>(pos);
    if (size_ == cap_)
    {
      return reallocate_and_fill(r, 1, ch);
    }
    char_traits::move(r + 1, r, end() - r);
    ++size_;
    *r = ch;
    return r;
  }

  // 在 pos 处插入 n 个元素
  template <class CharType, class CharTraits>
  typename basic_string<CharType, CharTraits>::iterator
  basic_string<CharType, CharTraits>::
      insert(const_iterator pos, size_type count, value_type ch)
  {
    iterator r = const_cast<iterator>(pos);
    if (count == 0)
      return r;
    if (cap_ - size_ < count)
    {
      return reallocate_and_fill(r, count, ch);
    }
    if (pos == end())
    {
      char_traits::fill(end(), ch, count);
      size_ += count;
      return r;
    }
    char_traits::move(r + count, r, count);
    char_traits::fill(r, ch, count);
    size_ += count;
    return r;
  }

  // 在 pos 处插入 [first, last) 内的元素
  template <class CharType, class CharTraits>
  template <class Iter>
  typename basic_string<CharType, CharTraits>::iterator
  basic_string<CharType, CharTraits>::
      insert(const_iterator pos, Iter first, Iter last)
  {
    iterator r = const_cast<iterator>(pos);
    const size_type len = mystl::distance(first, last);
    if (len == 0)
      return r;
    if (cap_ - size_ < len)
    {
      return reallocate_and_copy(r, first, last);
    }
    if (pos == end())
    {
      mystl::uninitialized_copy(first, last, end());
      size_ += len;
      return r;
    }
    char_traits::move(r + len, r, len);
    mystl::uninitialized_copy(first, last, r);
    size_ += len;
    return r;
  }

  // 在末尾添加 count 个 ch
  template <class CharType, class CharTraits>
  basic_string<CharType, CharTraits> &
  basic_string<CharType, CharTraits>::
      append(size_type count, value_type ch)
  {
    THROW_LENGTH_ERROR_IF(size_ > max_size() - count,
                          "basic_string<Char, Tratis>'s size too big");
    if (cap_ - size_ < count)
    {
      reallocate(count);
    }
    char_traits::fill(buffer_ + size_, ch, count);
    size_ += count;
    return *this;
  }

  // 在末尾添加 [str[pos] str[pos+count]) 一段
  template <class CharType, class CharTraits>
  basic_string<CharType, CharTraits> &
  basic_string<CharType, CharTraits>::
      append(const basic_string &str, size_type pos, size_type count)
  {
    THROW_LENGTH_ERROR_IF(size_ > max_size() - count,
                          "basic_string<Char, Tratis>'s size too big");
    if (count == 0)
      return *this;
    if (cap_ - size_ < count)
    {
      reallocate(count);
    }
    char_traits::copy(buffer_ + size_, str.buffer_ + pos, count);
    size_ += count;
    return *this;
  }

  // 在末尾添加 [s, s+count) 一段
  template <class CharType, class CharTraits>
  basic_string<CharType, CharTraits> &
  basic_string<CharType, CharTraits>::
      append(const_pointer s, size_type count)
  {
    THROW_LENGTH_ERROR_IF(size_ > max_size() - count,
                          "basic_string<Char, Tratis>'s size too big");
    if (cap_ - size_ < count)
    {
      reallocate(count);
    }
    char_traits::copy(buffer_ + size_, s, count);
    size_ += count;
    return *this;
  }

  // 删除 pos 处的元素
  template <class CharType, class CharTraits>
  typename basic_string<CharType, CharTraits>::iterator
  basic_string<CharType, CharTraits>::
      erase(const_iterator pos)
  {
    MYSTL_DEBUG(pos != end());
    iterator r = const_cast<iterator>(pos);
    char_traits::move(r, pos + 1, end() - pos - 1);
    --size_;
    return r;
  }

  // 删除 [first, last) 的元素
  template <class CharType, class CharTraits>
  typename basic_string<CharType, CharTraits>::iterator
  basic_string<CharType, CharTraits>::
      erase(const_iterator first, const_iterator last)
  {
    if (first == begin() && last == end())
    {
      clear();
      return end();
    }
    const size_type n = end() - last;
    iterator r = const_cast<iterator>(first);
    char_traits::move(r, last, n);
    size_ -= (last - first);
    return r;
  }

  // 重置容器大小
  template <class CharType, class CharTraits>
  void basic_string<CharType, CharTraits>::
      resize(size_type count, value_type ch)
  {
    if (count < size_)
    {
      erase(buffer_ + count, buffer_ + size_);
    }
    else
    {
      append(count - size_, ch);
    }
  }

  // 比较两个 basic_string，小于返回 -1，大于返回 1，等于返回 0
  template <class CharType, class CharTraits>
  int basic_string<CharType, CharTraits>::
      compare(const basic_string &other) const
  {
    return compare_cstr(buffer_, size_, other.buffer_, other.size_);
  }

  // 从 pos1 下标开始的 count1 个字符跟另一个 basic_string 比较
  template <class CharType, class CharTraits>
  int basic_string<CharType, CharTraits>::
      compare(size_type pos1, size_type count1, const basic_string &other) const
  {
    auto n1 = mystl::min(count1, size_ - pos1);
    return compare_cstr(buffer_ + pos1, n1, other.buffer_, other.size_);
  }

  // 从 pos1 下标开始的 count1 个字符跟另一个 basic_string 下标 pos2 开始的 count2 个字符比较
  template <class CharType, class CharTraits>
  int basic_string<CharType, CharTraits>::
      compare(size_type pos1, size_type count1, const basic_string &other,
              size_type pos2, size_type count2) const
  {
    auto n1 = mystl::min(count1, size_ - pos1);
    auto n2 = mystl::min(count2, other.size_ - pos2);
    return compare_cstr(buffer_, n1, other.buffer_, n2);
  }

  // 跟一个字符串比较
  template <class CharType, class CharTraits>
  int basic_string<CharType, CharTraits>::
      compare(const_pointer s) const
  {
    auto n2 = char_traits::length(s);
    return compare_cstr(buffer_, size_, s, n2);
  }

  // 从下标 pos1 开始的 count1 个字符跟另一个字符串比较
  template <class CharType, class CharTraits>
  int basic_string<CharType, CharTraits>::
      compare(size_type pos1, size_type count1, const_pointer s) const
  {
    auto n1 = mystl::min(count1, size_ - pos1);
    auto n2 = char_traits::length(s);
    return compare_cstr(buffer_, n1, s, n2);
  }

  // 从下标 pos1 开始的 count1 个字符跟另一个字符串的前 count2 个字符比较
  template <class CharType, class CharTraits>
  int basic_string<CharType, CharTraits>::
      compare(size_type pos1, size_type count1, const_pointer s, size_type count2) const
  {
    auto n1 = mystl::min(count1, size_ - pos1);
    return compare_cstr(buffer_, n1, s, count2);
  }

  // 反转 basic_string
  template <class CharType, class CharTraits>
  void basic_string<CharType, CharTraits>::
      reverse() noexcept
  {
    for (auto i = begin(), j = end(); i < j;)
    {
      mystl::iter_swap(i++, --j);
    }
  }

  // 交换两个 basic_string
  template <class CharType, class CharTraits>
  void basic_string<CharType, CharTraits>::
      swap(basic_string &rhs) noexcept
  {
    if (this != &rhs)
    {
      mystl::swap(buffer_, rhs.buffer_);
      mystl::swap(size_, rhs.size_);
      mystl::swap(cap_, rhs.cap_);
    }
  }

  // 从下标 pos 开始查找字符为 ch 的元素，若找到返回其下标，否则返回 npos
  template <class CharType, class CharTraits>
  typename basic_string<CharType, CharTraits>::size_type
  basic_string<CharType, CharTraits>::
      find(value_type ch, size_type pos) const noexcept
  {
    for (auto i = pos; i < size_; ++i)
    {
      if (*(buffer_ + i) == ch)
        return i;
    }
    return npos;
  }

  // 从下标 pos 开始查找字符串 str，若找到返回起始位置的下标，否则返回 npos
  template <class CharType, class CharTraits>
  typename basic_string<CharType, CharTraits>::size_type
  basic_string<CharType, CharTraits>::
      find(const_pointer str, size_type pos) const noexcept
  {
    const auto len = char_traits::length(str);
    if (len == 0)
      return pos;
    if (size_ - pos < len)
      return npos;
    const auto left = size_ - len;
    for (auto i = pos; i <= left; ++i)
    {
      if (*(buffer_ + i) == *str)
      {
        size_type j = 1;
        for (; j < len; ++j)
        {
          if (*(buffer_ + i + j) != *(str + j))
            break;
        }
        if (j == len)
          return i;
      }
    }
    return npos;
  }

  // 从下标 pos 开始查找字符串 str 的前 count 个字符，若找到返回起始位置的下标，否则返回 npos
  template <class CharType, class CharTraits>
  typename basic_string<CharType, CharTraits>::size_type
  basic_string<CharType, CharTraits>::
      find(const_pointer str, size_type pos, size_type count) const noexcept
  {
    if (count == 0)
      return pos;
    if (size_ - pos < count)
      return npos;
    const auto left = size_ - count;
    for (auto i = pos; i <= left; ++i)
    {
      if (*(buffer_ + i) == *str)
      {
        size_type j = 1;
        for (; j < count; ++j)
        {
          if (*(buffer_ + i + j) != *(str + j))
            break;
        }
        if (j == count)
          return i;
      }
    }
    return npos;
  }

  // 从下标 pos 开始查找字符串 str，若找到返回起始位置的下标，否则返回 npos
  template <class CharType, class CharTraits>
  typename basic_string<CharType, CharTraits>::size_type
  basic_string<CharType, CharTraits>::
      find(const basic_string &str, size_type pos) const noexcept
  {
    const size_type count = str.size_;
    if (count == 0)
      return pos;
    if (size_ - pos < count)
      return npos;
    const auto left = size_ - count;
    for (auto i = pos; i <= left; ++i)
    {
      if (*(buffer_ + i) == str.front())
      {
        size_type j = 1;
        for (; j < count; ++j)
        {
          if (*(buffer_ + i + j) != str[j])
            break;
        }
        if (j == count)
          return i;
      }
    }
    return npos;
  }

  // 从下标 pos 开始反向查找值为 ch 的元素，与 find 类似
  template <class CharType, class CharTraits>
  typename basic_string<CharType, CharTraits>::size_type
  basic_string<CharType, CharTraits>::
      rfind(value_type ch, size_type pos) const noexcept
  {
    if (pos >= size_)
      pos = size_ - 1;
    for (auto i = pos; i != 0; --i)
    {
      if (*(buffer_ + i) == ch)
        return i;
    }
    return front() == ch ? 0 : npos;
  }

  // 从下标 pos 开始反向查找字符串 str，与 find 类似
  template <class CharType, class CharTraits>
  typename basic_string<CharType, CharTraits>::size_type
  basic_string<CharType, CharTraits>::
      rfind(const_pointer str, size_type pos) const noexcept
  {
    if (pos >= size_)
      pos = size_ - 1;
    const size_type len = char_traits::length(str);
    switch (len)
    {
    case 0:
      return pos;
    case 1:
    {
      for (auto i = pos; i != 0; --i)
      {
        if (*(buffer_ + i) == *str)
          return i;
      }
      return front() == *str ? 0 : npos;
    }
    default:
    { // len >= 2
      for (auto i = pos; i >= len - 1; --i)
      {
        if (*(buffer_ + i) == *(str + len - 1))
        {
          size_type j = 1;
          for (; j < len; ++j)
          {
            if (*(buffer_ + i - j) != *(str + len - j - 1))
              break;
          }
          if (j == len)
            return i - len + 1;
        }
      }
      break;
    }
    }
    return npos;
  }

  // 从下标 pos 开始反向查找字符串 str 前 count 个字符，与 find 类似
  template <class CharType, class CharTraits>
  typename basic_string<CharType, CharTraits>::size_type
  basic_string<CharType, CharTraits>::
      rfind(const_pointer str, size_type pos, size_type count) const noexcept
  {
    if (count == 0)
      return pos;
    if (pos >= size_)
      pos = size_ - 1;
    if (pos < count - 1)
      return npos;
    for (auto i = pos; i >= count - 1; --i)
    {
      if (*(buffer_ + i) == *(str + count - 1))
      {
        size_type j = 1;
        for (; j < count; ++j)
        {
          if (*(buffer_ + i - j) != *(str + count - j - 1))
            break;
        }
        if (j == count)
          return i - count + 1;
      }
    }
    return npos;
  }

  // 从下标 pos 开始反向查找字符串 str，与 find 类似
  template <class CharType, class CharTraits>
  typename basic_string<CharType, CharTraits>::size_type
  basic_string<CharType, CharTraits>::
      rfind(const basic_string &str, size_type pos) const noexcept
  {
    const size_type count = str.size_;
    if (pos >= size_)
      pos = size_ - 1;
    if (count == 0)
      return pos;
    if (pos < count - 1)
      return npos;
    for (auto i = pos; i >= count - 1; --i)
    {
      if (*(buffer_ + i) == str[count - 1])
      {
        size_type j = 1;
        for (; j < count; ++j)
        {
          if (*(buffer_ + i - j) != str[count - j - 1])
            break;
        }
        if (j == count)
          return i - count + 1;
      }
    }
    return npos;
  }

  // 从下标 pos 开始查找 ch 出现的第一个位置
  template <class CharType, class CharTraits>
  typename basic_string<CharType, CharTraits>::size_type
  basic_string<CharType, CharTraits>::
      find_first_of(value_type ch, size_type pos) const noexcept
  {
    for (auto i = pos; i < size_; ++i)
    {
      if (*(buffer_ + i) == ch)
        return i;
    }
    return npos;
  }

  // 从下标 pos 开始查找字符串 s 其中的一个字符出现的第一个位置
  template <class CharType, class CharTraits>
  typename basic_string<CharType, CharTraits>::size_type
  basic_string<CharType, CharTraits>::
      find_first_of(const_pointer s, size_type pos) const noexcept
  {
    const size_type len = char_traits::length(s);
    for (auto i = pos; i < size_; ++i)
    {
      value_type ch = *(buffer_ + i);
      for (size_type j = 0; j < len; ++j)
      {
        if (ch == *(s + j))
          return i;
      }
    }
    return npos;
  }

  // 从下标 pos 开始查找字符串 s
  template <class CharType, class CharTraits>
  typename basic_string<CharType, CharTraits>::size_type
  basic_string<CharType, CharTraits>::
      find_first_of(const_pointer s, size_type pos, size_type count) const noexcept
  {
    for (auto i = pos; i < size_; ++i)
    {
      value_type ch = *(buffer_ + i);
      for (size_type j = 0; j < count; ++j)
      {
        if (ch == *(s + j))
          return i;
      }
    }
    return npos;
  }

  // 从下标 pos 开始查找字符串 str 其中一个字符出现的第一个位置
  template <class CharType, class CharTraits>
  typename basic_string<CharType, CharTraits>::size_type
  basic_string<CharType, CharTraits>::
      find_first_of(const basic_string &str, size_type pos) const noexcept
  {
    for (auto i = pos; i < size_; ++i)
    {
      value_type ch = *(buffer_ + i);
      for (size_type j = 0; j < str.size_; ++j)
      {
        if (ch == str[j])
          return i;
      }
    }
    return npos;
  }

  // 从下标 pos 开始查找与 ch 不相等的第一个位置
  template <class CharType, class CharTraits>
  typename basic_string<CharType, CharTraits>::size_type
  basic_string<CharType, CharTraits>::
      find_first_not_of(value_type ch, size_type pos) const noexcept
  {
    for (auto i = pos; i < size_; ++i)
    {
      if (*(buffer_ + i) != ch)
        return i;
    }
    return npos;
  }

  // 从下标 pos 开始查找与字符串 s 其中一个字符不相等的第一个位置
  template <class CharType, class CharTraits>
  typename basic_string<CharType, CharTraits>::size_type
  basic_string<CharType, CharTraits>::
      find_first_not_of(const_pointer s, size_type pos) const noexcept
  {
    const size_type len = char_traits::length(s);
    for (auto i = pos; i < size_; ++i)
    {
      value_type ch = *(buffer_ + i);
      for (size_type j = 0; j < len; ++j)
      {
        if (ch != *(s + j))
          return i;
      }
    }
    return npos;
  }

  // 从下标 pos 开始查找与字符串 s 前 count 个字符中不相等的第一个位置
  template <class CharType, class CharTraits>
  typename basic_string<CharType, CharTraits>::size_type
  basic_string<CharType, CharTraits>::
      find_first_not_of(const_pointer s, size_type pos, size_type count) const noexcept
  {
    for (auto i = pos; i < size_; ++i)
    {
      value_type ch = *(buffer_ + i);
      for (size_type j = 0; j < count; ++j)
      {
        if (ch != *(s + j))
          return i;
      }
    }
    return npos;
  }

  // 从下标 pos 开始查找与字符串 str 的字符中不相等的第一个位置
  template <class CharType, class CharTraits>
  typename basic_string<CharType, CharTraits>::size_type
  basic_string<CharType, CharTraits>::
      find_first_not_of(const basic_string &str, size_type pos) const noexcept
  {
    for (auto i = pos; i < size_; ++i)
    {
      value_type ch = *(buffer_ + i);
      for (size_type j = 0; j < str.size_; ++j)
      {
        if (ch != str[j])
          return i;
      }
    }
    return npos;
  }

  // 从下标 pos 开始查找与 ch 相等的最后一个位置
  template <class CharType, class CharTraits>
  typename basic_string<CharType, CharTraits>::size_type
  basic_string<CharType, CharTraits>::
      find_last_of(value_type ch, size_type pos) const noexcept
  {
    for (auto i = size_ - 1; i >= pos; --i)
    {
      if (*(buffer_ + i) == ch)
        return i;
    }
    return npos;
  }

  // 从下标 pos 开始查找与字符串 s 其中一个字符相等的最后一个位置
  template <class CharType, class CharTraits>
  typename basic_string<CharType, CharTraits>::size_type
  basic_string<CharType, CharTraits>::
      find_last_of(const_pointer s, size_type pos) const noexcept
  {
    const size_type len = char_traits::length(s);
    for (auto i = size_ - 1; i >= pos; --i)
    {
      value_type ch = *(buffer_ + i);
      for (size_type j = 0; j < len; ++j)
      {
        if (ch == *(s + j))
          return i;
      }
    }
    return npos;
  }

  // 从下标 pos 开始查找与字符串 s 前 count 个字符中相等的最后一个位置
  template <class CharType, class CharTraits>
  typename basic_string<CharType, CharTraits>::size_type
  basic_string<CharType, CharTraits>::
      find_last_of(const_pointer s, size_type pos, size_type count) const noexcept
  {
    for (auto i = size_ - 1; i >= pos; --i)
    {
      value_type ch = *(buffer_ + i);
      for (size_type j = 0; j < count; ++j)
      {
        if (ch == *(s + j))
          return i;
      }
    }
    return npos;
  }

  // 从下标 pos 开始查找与字符串 str 字符中相等的最后一个位置
  template <class CharType, class CharTraits>
  typename basic_string<CharType, CharTraits>::size_type
  basic_string<CharType, CharTraits>::
      find_last_of(const basic_string &str, size_type pos) const noexcept
  {
    for (auto i = size_ - 1; i >= pos; --i)
    {
      value_type ch = *(buffer_ + i);
      for (size_type j = 0; j < str.size_; ++j)
      {
        if (ch == str[j])
          return i;
      }
    }
    return npos;
  }

  // 从下标 pos 开始查找与 ch 字符不相等的最后一个位置
  template <class CharType, class CharTraits>
  typename basic_string<CharType, CharTraits>::size_type
  basic_string<CharType, CharTraits>::
      find_last_not_of(value_type ch, size_type pos) const noexcept
  {
    for (auto i = size_ - 1; i >= pos; --i)
    {
      if (*(buffer_ + i) != ch)
        return i;
    }
    return npos;
  }

  // 从下标 pos 开始查找与字符串 s 的字符中不相等的最后一个位置
  template <class CharType, class CharTraits>
  typename basic_string<CharType, CharTraits>::size_type
  basic_string<CharType, CharTraits>::
      find_last_not_of(const_pointer s, size_type pos) const noexcept
  {
    const size_type len = char_traits::length(s);
    for (auto i = size_ - 1; i >= pos; --i)
    {
      value_type ch = *(buffer_ + i);
      for (size_type j = 0; j < len; ++j)
      {
        if (ch != *(s + j))
          return i;
      }
    }
    return npos;
  }

  // 从下标 pos 开始查找与字符串 s 前 count 个字符中不相等的最后一个位置
  template <class CharType, class CharTraits>
  typename basic_string<CharType, CharTraits>::size_type
  basic_string<CharType, CharTraits>::
      find_last_not_of(const_pointer s, size_type pos, size_type count) const noexcept
  {
    for (auto i = size_ - 1; i >= pos; --i)
    {
      value_type ch = *(buffer_ + i);
      for (size_type j = 0; j < count; ++j)
      {
        if (ch != *(s + j))
          return i;
      }
    }
    return npos;
  }

  // 从下标 pos 开始查找与字符串 str 字符中不相等的最后一个位置
  template <class CharType, class CharTraits>
  typename basic_string<CharType, CharTraits>::size_type
  basic_string<CharType, CharTraits>::
      find_last_not_of(const basic_string &str, size_type pos) const noexcept
  {
    for (auto i = size_ - 1; i >= pos; --i)
    {
      value_type ch = *(buffer_ + i);
      for (size_type j = 0; j < str.size_; ++j)
      {
        if (ch != str[j])
          return i;
      }
    }
    return npos;
  }

  // 返回从下标 pos 开始字符为 ch 的元素出现的次数
  template <class CharType, class CharTraits>
  typename basic_string<CharType, CharTraits>::size_type
  basic_string<CharType, CharTraits>::
      count(value_type ch, size_type pos) const noexcept
  {
    size_type n = 0;
    for (auto i = pos; i < size_; ++i)
    {
      if (*(buffer_ + i) == ch)
        ++n;
    }
    return n;
  }

  /*****************************************************************************************/
  // helper function

  // 尝试初始化一段 buffer，若分配失败则忽略，不会抛出异常
  template <class CharType, class CharTraits>
  void basic_string<CharType, CharTraits>::
      try_init() noexcept
  {
    try
    {
      buffer_ = data_allocator::allocate(static_cast<size_type>(STRING_INIT_SIZE));
      size_ = 0;
      cap_ = 0;
    }
    catch (...)
    {
      buffer_ = nullptr;
      size_ = 0;
      cap_ = 0;
      // no throw
    }
  }

  // fill_init 函数
  template <class CharType, class CharTraits>
  void basic_string<CharType, CharTraits>::
      fill_init(size_type n, value_type ch)
  {
    const auto init_size = mystl::max(static_cast<size_type>(STRING_INIT_SIZE), n + 1);
    buffer_ = data_allocator::allocate(init_size);
    char_traits::fill(buffer_, ch, n);
    size_ = n;
    cap_ = init_size;
  }

  // copy_init 函数
  template <class CharType, class CharTraits>
  template <class Iter>
  void basic_string<CharType, CharTraits>::
      copy_init(Iter first, Iter last, mystl::input_iterator_tag)
  {
    size_type n = mystl::distance(first, last);
    const auto init_size = mystl::max(static_cast<size_type>(STRING_INIT_SIZE), n + 1);
    try
    {
      buffer_ = data_allocator::allocate(init_size);
      size_ = n;
      cap_ = init_size;
    }
    catch (...)
    {
      buffer_ = nullptr;
      size_ = 0;
      cap_ = 0;
      throw;
    }
    for (; n > 0; --n, ++first)
      append(*first);
  }

  template <class CharType, class CharTraits>
  template <class Iter>
  void basic_string<CharType, CharTraits>::
      copy_init(Iter first, Iter last, mystl::forward_iterator_tag)
  {
    const size_type n = mystl::distance(first, last);
    const auto init_size = mystl::max(static_cast<size_type>(STRING_INIT_SIZE), n + 1);
    try
    {
      buffer_ = data_allocator::allocate(init_size);
      size_ = n;
      cap_ = init_size;
      mystl::uninitialized_copy(first, last, buffer_);
    }
    catch (...)
    {
      buffer_ = nullptr;
      size_ = 0;
      cap_ = 0;
      throw;
    }
  }

  // init_from 函数
  template <class CharType, class CharTraits>
  void basic_string<CharType, CharTraits>::
      init_from(const_pointer src, size_type pos, size_type count)
  {
    const auto init_size = mystl::max(static_cast<size_type>(STRING_INIT_SIZE), count + 1);
    buffer_ = data_allocator::allocate(init_size);
    char_traits::copy(buffer_, src + pos, count);
    size_ = count;
    cap_ = init_size;
  }

  // destroy_buffer 函数
  template <class CharType, class CharTraits>
  void basic_string<CharType, CharTraits>::
      destroy_buffer()
  {
    if (buffer_ != nullptr)
    {
      data_allocator::deallocate(buffer_, cap_);
      buffer_ = nullptr;
      size_ = 0;
      cap_ = 0;
    }
  }

  // to_raw_pointer 函数
  template <class CharType, class CharTraits>
  typename basic_string<CharType, CharTraits>::const_pointer
  basic_string<CharType, CharTraits>::
      to_raw_pointer() const
  {
    *(buffer_ + size_) = value_type();
    return buffer_;
  }

  // reinsert 函数
  template <class CharType, class CharTraits>
  void basic_string<CharType, CharTraits>::
      reinsert(size_type size)
  {
    auto new_buffer = data_allocator::allocate(size);
    try
    {
      char_traits::move(new_buffer, buffer_, size);
    }
    catch (...)
    {
      data_allocator::deallocate(new_buffer);
    }
    buffer_ = new_buffer;
    size_ = size;
    cap_ = size;
  }

  // append_range，末尾追加一段 [first, last) 内的字符
  template <class CharType, class CharTraits>
  template <class Iter>
  basic_string<CharType, CharTraits> &
  basic_string<CharType, CharTraits>::
      append_range(Iter first, Iter last)
  {
    const size_type n = mystl::distance(first, last);
    THROW_LENGTH_ERROR_IF(size_ > max_size() - n,
                          "basic_string<Char, Tratis>'s size too big");
    if (cap_ - size_ < n)
    {
      reallocate(n);
    }
    mystl::uninitialized_copy_n(first, n, buffer_ + size_);
    size_ += n;
    return *this;
  }

  template <class CharType, class CharTraits>
  int basic_string<CharType, CharTraits>::
      compare_cstr(const_pointer s1, size_type n1, const_pointer s2, size_type n2) const
  {
    auto rlen = mystl::min(n1, n2);
    auto res = char_traits::compare(s1, s2, rlen);
    if (res != 0)
      return res;
    if (n1 < n2)
      return -1;
    if (n1 > n2)
      return 1;
    return 0;
  }

  // 把 first 开始的 count1 个字符替换成 str 开始的 count2 个字符
  template <class CharType, class CharTraits>
  basic_string<CharType, CharTraits> &
  basic_string<CharType, CharTraits>::
      replace_cstr(const_iterator first, size_type count1, const_pointer str, size_type count2)
  {
    if (static_cast<size_type>(cend() - first) < count1)
    {
      count1 = cend() - first;
    }
    if (count1 < count2)
    {
      const size_type add = count2 - count1;
      THROW_LENGTH_ERROR_IF(size_ > max_size() - add,
                            "basic_string<Char, Traits>'s size too big");
      if (size_ > cap_ - add)
      {
        reallocate(add);
      }
      pointer r = const_cast<pointer>(first);
      char_traits::move(r + count2, first + count1, end() - (first + count1));
      char_traits::copy(r, str, count2);
      size_ += add;
    }
    else
    {
      pointer r = const_cast<pointer>(first);
      char_traits::move(r + count2, first + count1, end() - (first + count1));
      char_traits::copy(r, str, count2);
      size_ -= (count1 - count2);
    }
    return *this;
  }

  // 把 first 开始的 count1 个字符替换成 count2 个 ch 字符
  template <class CharType, class CharTraits>
  basic_string<CharType, CharTraits> &
  basic_string<CharType, CharTraits>::
      replace_fill(const_iterator first, size_type count1, size_type count2, value_type ch)
  {
    if (static_cast<size_type>(cend() - first) < count1)
    {
      count1 = cend() - first;
    }
    if (count1 < count2)
    {
      const size_type add = count2 - count1;
      THROW_LENGTH_ERROR_IF(size_ > max_size() - add,
                            "basic_string<Char, Traits>'s size too big");
      if (size_ > cap_ - add)
      {
        reallocate(add);
      }
      pointer r = const_cast<pointer>(first);
      char_traits::move(r + count2, first + count1, end() - (first + count1));
      char_traits::fill(r, ch, count2);
      size_ += add;
    }
    else
    {
      pointer r = const_cast<pointer>(first);
      char_traits::move(r + count2, first + count1, end() - (first + count1));
      char_traits::fill(r, ch, count2);
      size_ -= (count1 - count2);
    }
    return *this;
  }

  // 把 [first, last) 的字符替换成 [first2, last2)
  template <class CharType, class CharTraits>
  template <class Iter>
  basic_string<CharType, CharTraits> &
  basic_string<CharType, CharTraits>::
      replace_copy(const_iterator first, const_iterator last, Iter first2, Iter last2)
  {
    size_type len1 = last - first;
    size_type len2 = last2 - first2;
    if (len1 < len2)
    {
      const size_type add = len2 - len1;
      THROW_LENGTH_ERROR_IF(size_ > max_size() - add,
                            "basic_string<Char, Traits>'s size too big");
      if (size_ > cap_ - add)
      {
        reallocate(add);
      }
      pointer r = const_cast<pointer>(first);
      char_traits::move(r + len2, first + len1, end() - (first + len1));
      char_traits::copy(r, first2, len2);
      size_ += add;
    }
    else
    {
      pointer r = const_cast<pointer>(first);
      char_traits::move(r + len2, first + len1, end() - (first + len1));
      char_traits::copy(r, first2, len2);
      size_ -= (len1 - len2);
    }
    return *this;
  }

  // reallocate 函数
  template <class CharType, class CharTraits>
  void basic_string<CharType, CharTraits>::
      reallocate(size_type need)
  {
    const auto new_cap = mystl::max(cap_ + need, cap_ + (cap_ >> 1));
    auto new_buffer = data_allocator::allocate(new_cap);
    char_traits::move(new_buffer, buffer_, size_);
    data_allocator::deallocate(buffer_);
    buffer_ = new_buffer;
    cap_ = new_cap;
  }

  // reallocate_and_fill 函数
  template <class CharType, class CharTraits>
  typename basic_string<CharType, CharTraits>::iterator
  basic_string<CharType, CharTraits>::
      reallocate_and_fill(iterator pos, size_type n, value_type ch)
  {
    const auto r = pos - buffer_;
    const auto old_cap = cap_;
    const auto new_cap = mystl::max(old_cap + n, old_cap + (old_cap >> 1));
    auto new_buffer = data_allocator::allocate(new_cap);
    auto e1 = char_traits::move(new_buffer, buffer_, r) + r;
    auto e2 = char_traits::fill(e1, ch, n) + n;
    char_traits::move(e2, buffer_ + r, size_ - r);
    data_allocator::deallocate(buffer_, old_cap);
    buffer_ = new_buffer;
    size_ += n;
    cap_ = new_cap;
    return buffer_ + r;
  }

  // reallocate_and_copy 函数
  template <class CharType, class CharTraits>
  typename basic_string<CharType, CharTraits>::iterator
  basic_string<CharType, CharTraits>::
      reallocate_and_copy(iterator pos, const_iterator first, const_iterator last)
  {
    const auto r = pos - buffer_;
    const auto old_cap = cap_;
    const size_type n = mystl::distance(first, last);
    const auto new_cap = mystl::max(old_cap + n, old_cap + (old_cap >> 1));
    auto new_buffer = data_allocator::allocate(new_cap);
    auto e1 = char_traits::move(new_buffer, buffer_, r) + r;
    auto e2 = mystl::uninitialized_copy_n(first, n, e1) + n;
    char_traits::move(e2, buffer_ + r, size_ - r);
    data_allocator::deallocate(buffer_, old_cap);
    buffer_ = new_buffer;
    size_ += n;
    cap_ = new_cap;
    return buffer_ + r;
  }

  /*****************************************************************************************/
  // 重载全局操作符

  // 重载 operator+
  template <class CharType, class CharTraits>
  basic_string<CharType, CharTraits>
  operator+(const basic_string<CharType, CharTraits> &lhs,
            const basic_string<CharType, CharTraits> &rhs)
  {
    basic_string<CharType, CharTraits> tmp(lhs);
    tmp.append(rhs);
    return tmp;
  }

  template <class CharType, class CharTraits>
  basic_string<CharType, CharTraits>
  operator+(const CharType *lhs, const basic_string<CharType, CharTraits> &rhs)
  {
    basic_string<CharType, CharTraits> tmp(lhs);
    tmp.append(rhs);
    return tmp;
  }

  template <class CharType, class CharTraits>
  basic_string<CharType, CharTraits>
  operator+(CharType ch, const basic_string<CharType, CharTraits> &rhs)
  {
    basic_string<CharType, CharTraits> tmp(1, ch);
    tmp.append(rhs);
    return tmp;
  }

  template <class CharType, class CharTraits>
  basic_string<CharType, CharTraits>
  operator+(const basic_string<CharType, CharTraits> &lhs, const CharType *rhs)
  {
    basic_string<CharType, CharTraits> tmp(lhs);
    tmp.append(rhs);
    return tmp;
  }

  template <class CharType, class CharTraits>
  basic_string<CharType, CharTraits>
  operator+(const basic_string<CharType, CharTraits> &lhs, CharType ch)
  {
    basic_string<CharType, CharTraits> tmp(lhs);
    tmp.append(1, ch);
    return tmp;
  }

  template <class CharType, class CharTraits>
  basic_string<CharType, CharTraits>
  operator+(basic_string<CharType, CharTraits> &&lhs,
            const basic_string<CharType, CharTraits> &rhs)
  {
    basic_string<CharType, CharTraits> tmp(mystl::move(lhs));
    tmp.append(rhs);
    return tmp;
  }

  template <class CharType, class CharTraits>
  basic_string<CharType, CharTraits>
  operator+(const basic_string<CharType, CharTraits> &lhs,
            basic_string<CharType, CharTraits> &&rhs)
  {
    basic_string<CharType, CharTraits> tmp(mystl::move(rhs));
    tmp.insert(tmp.begin(), lhs.begin(), lhs.end());
    return tmp;
  }

  template <class CharType, class CharTraits>
  basic_string<CharType, CharTraits>
  operator+(basic_string<CharType, CharTraits> &&lhs,
            basic_string<CharType, CharTraits> &&rhs)
  {
    basic_string<CharType, CharTraits> tmp(mystl::move(lhs));
    tmp.append(rhs);
    return tmp;
  }

  template <class CharType, class CharTraits>
  basic_string<CharType, CharTraits>
  operator+(const CharType *lhs, basic_string<CharType, CharTraits> &&rhs)
  {
    basic_string<CharType, CharTraits> tmp(mystl::move(rhs));
    tmp.insert(tmp.begin(), lhs, lhs + char_traits<CharType>::length(lhs));
    return tmp;
  }

  template <class CharType, class CharTraits>
  basic_string<CharType, CharTraits>
  operator+(CharType ch, basic_string<CharType, CharTraits> &&rhs)
  {
    basic_string<CharType, CharTraits> tmp(mystl::move(rhs));
    tmp.insert(tmp.begin(), ch);
    return tmp;
  }

  template <class CharType, class CharTraits>
  basic_string<CharType, CharTraits>
  operator+(basic_string<CharType, CharTraits> &&lhs, const CharType *rhs)
  {
    basic_string<CharType, CharTraits> tmp(mystl::move(lhs));
    tmp.append(rhs);
    return tmp;
  }

  template <class CharType, class CharTraits>
  basic_string<CharType, CharTraits>
  operator+(basic_string<CharType, CharTraits> &&lhs, CharType ch)
  {
    basic_string<CharType, CharTraits> tmp(mystl::move(lhs));
    tmp.append(1, ch);
    return tmp;
  }

  // 重载比较操作符
  template <class CharType, class CharTraits>
  bool operator==(const basic_string<CharType, CharTraits> &lhs,
                  const basic_string<CharType, CharTraits> &rhs)
  {
    return lhs.size() == rhs.size() && lhs.compare(rhs) == 0;
  }

  template <class CharType, class CharTraits>
  bool operator!=(const basic_string<CharType, CharTraits> &lhs,
                  const basic_string<CharType, CharTraits> &rhs)
  {
    return lhs.size() != rhs.size() || lhs.compare(rhs) != 0;
  }

  template <class CharType, class CharTraits>
  bool operator<(const basic_string<CharType, CharTraits> &lhs,
                 const basic_string<CharType, CharTraits> &rhs)
  {
    return lhs.compare(rhs) < 0;
  }

  template <class CharType, class CharTraits>
  bool operator<=(const basic_string<CharType, CharTraits> &lhs,
                  const basic_string<CharType, CharTraits> &rhs)
  {
    return lhs.compare(rhs) <= 0;
  }

  template <class CharType, class CharTraits>
  bool operator>(const basic_string<CharType, CharTraits> &lhs,
                 const basic_string<CharType, CharTraits> &rhs)
  {
    return lhs.compare(rhs) > 0;
  }

  template <class CharType, class CharTraits>
  bool operator>=(const basic_string<CharType, CharTraits> &lhs,
                  const basic_string<CharType, CharTraits> &rhs)
  {
    return lhs.compare(rhs) >= 0;
  }

  // 重载 mystl 的 swap
  template <class CharType, class CharTraits>
  void swap(basic_string<CharType, CharTraits> &lhs,
            basic_string<CharType, CharTraits> &rhs) noexcept
  {
    lhs.swap(rhs);
  }

  // 特化 mystl::hash
  template <class CharType, class CharTraits>
  struct hash<basic_string<CharType, CharTraits>>
  {
    size_t operator()(const basic_string<CharType, CharTraits> &str)
    {
      return bitwise_hash((const unsigned char *)str.c_str(),
                          str.size() * sizeof(CharType));
    }
  };

} // namespace mystl
DEAL_II_NAMESPACE_CLOSE
#endif // !MYTINYSTL_BASIC_STRING_H_
